Решето Ератосфена. Прості числа.
Решето Ератосфена.Прості числа Автор статті : Олійниченко Данило. Тема дослідження Проблема дослідження Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа , що був створений давньогрецьким математиком Ератосфеном. Гіпотеза дослідження Ми освоемо метод "Решета Ератосфена" для находження простих чисел,але,скоріш за все, не зможемо знайти найбільше просте число. Мета дослідження Я спробую пояснити закономірність знаходження простих чисел через освоєння методу "Решето Ератосфена". Хід і результати дослідження Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N. #Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …). #Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …). #Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …). #Повторюємо операцію поки не буде досягнуто число N: #*Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому. Числа, які залишилися незакресленими після цієї процедури - прості[1]. Розглянемо приклад для n = 20 Запишемо натуральні числа від 2 до 20 в рядок: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з {\displaystyle 2^{2}=4}): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з {\displaystyle 3^{2}=9}): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 Sieve_of_Eratosthenes_animation.gif (кожне п’яте, починаючи з {\displaystyle 5^{2}=25}). І т. д. Необхідно викреслити кратні для всіх простих чисел {\displaystyle p}, для яких {\displaystyle p^{2}\leq n}. В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для {\displaystyle n=20} вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими. Алгоритм решета Ератосфена у вигляді програми на псевдокоді для пошуку простих чисел менших 1 000 000 : limit = 1000000 // початково вважаємо, що всі числа прості // присвоєння змінній типу стрічка символів sieve$ рядка, який складається з 1000000 літер "Р", sieve$ = string of the character "P" with length limit prime = 2 // 2 – перше просте число repeat while prime² < limit // зміна літер "Р", порядковий номер (індекс) яких кратний prime (за виключенням індекса prime), на "N" set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N" // змінній prime присвоюється індекс наступної "Р" в стрічці sieve$ prime = index of the next instance of "P" in sieve$ after index prime end repeat Висновки Мені дуже сподобалося проводити дослідження з простими чісламі.Я спробував «вловити», відсіяти прості числа від складових, користуючись «Решетом Ератосфена» Корисні ресурси Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld. Доповнення до статті